package com.basic.fft;

import java.io.*;
import java.util.*;
import java.util.stream.*;

public class FFT {

    private static final double PI = 3.1416;

    private static void swap(double[] arr, int i, int j) {
        double temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static void bitrp(double[] xreal, double[] ximag, int n) {
        int i, j, a, b, p;
        for (i = 1, p = 0; i < n; i *= 2) {
            p++;
        }
        for (i = 0; i < n; i++) {
            a = i;
            b = 0;
            for (j = 0; j < p; j++) {
                b = (b << 1) + (a & 1);
                a >>= 1;
            }
            if (b > i) {
                swap(xreal, i, b);
                swap(ximag, i, b);
            }
        }
    }

    private static void FFT(double[] xreal, double[] ximag, int n, int N) {
        double[] wreal = new double[N / 2];
        double[] wimag = new double[N / 2];
        double treal, timag, ureal, uimag, arg;
        int m, k, j, t, index1, index2;

        bitrp(xreal, ximag, n);

        arg = -2 * PI / n;
        treal = Math.cos(arg);
        timag = Math.sin(arg);
        wreal[0] = 1.0;
        wimag[0] = 0.0;
        for (j = 1; j < n / 2; j++) {
            wreal[j] = wreal[j - 1] * treal - wimag[j - 1] * timag;
            wimag[j] = wreal[j - 1] * timag + wimag[j - 1] * treal;
        }

        for (m = 2; m <= n; m *= 2) {
            for (k = 0; k < n; k += m) {
                for (j = 0; j < m / 2; j++) {
                    index1 = k + j;
                    index2 = index1 + m / 2;
                    t = n * j / m;
                    treal = wreal[t] * xreal[index2] - wimag[t] * ximag[index2];
                    timag = wreal[t] * ximag[index2] + wimag[t] * xreal[index2];
                    ureal = xreal[index1];
                    uimag = ximag[index1];
                    xreal[index1] = ureal + treal;
                    ximag[index1] = uimag + timag;
                    xreal[index2] = ureal - treal;
                    ximag[index2] = uimag - timag;
                }
            }
        }
    }

    private static void IFFT(double[] xreal, double[] ximag, int n, int N) {
        double[] wreal = new double[N / 2];
        double[] wimag = new double[N / 2];
        double treal, timag, ureal, uimag, arg;
        int m, k, j, t, index1, index2;

        bitrp(xreal, ximag, n);

        arg = 2 * PI / n;
        treal = Math.cos(arg);
        timag = Math.sin(arg);
        wreal[0] = 1.0;
        wimag[0] = 0.0;
        for (j = 1; j < n / 2; j++) {
            wreal[j] = wreal[j - 1] * treal - wimag[j - 1] * timag;
            wimag[j] = wreal[j - 1] * timag + wimag[j - 1] * treal;
        }

        for (m = 2; m <= n; m *= 2) {
            for (k = 0; k < n; k += m) {
                for (j = 0; j < m / 2; j++) {
                    index1 = k + j;
                    index2 = index1 + m / 2;
                    t = n * j / m;
                    treal = wreal[t] * xreal[index2] - wimag[t] * ximag[index2];
                    timag = wreal[t] * ximag[index2] + wimag[t] * xreal[index2];
                    ureal = xreal[index1];
                    uimag = ximag[index1];
                    xreal[index1] = ureal + treal;
                    ximag[index1] = uimag + timag;
                    xreal[index2] = ureal - treal;
                    ximag[index2] = uimag - timag;
                }
            }
        }

        for (j = 0; j < n; j++) {
            xreal[j] /= n;
            ximag[j] /= n;
        }
    }

    private static void FFT_test() throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));
        List<Double> V = new ArrayList<>();
        String line;
        while ((line = br.readLine()) != null) {
            V.add(Double.parseDouble(line.trim()));
        }
        br.close();

        int n = V.size();
        System.out.println("length= " + n);

        int k = (int) (Math.log(n) / Math.log(2));
        int N = (int) Math.pow(2, (k + 1));
        double[] xreal = new double[N];
        double[] ximag = new double[N];
        for (int i = 0; i < n; i++) {
            xreal[i] = V.get(i);
            ximag[i] = 0;
        }
        for (int i = n; i < N; i++) {
            xreal[i] = 0;
            ximag[i] = 0;
        }

        BufferedWriter bw = new BufferedWriter(new FileWriter("java-output.txt"));
        FFT(xreal, ximag, n, N);
        for (int i = 0; i < n; i++) {
            bw.write(i + "     " + xreal[i] + "     " + ximag[i]);
            System.out.println(i+": "+xreal[i]);
            bw.newLine();
        }
        bw.close();
    }

    public static void main(String[] args) {
        try {
            FFT_test();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}
